import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @program: data_structures_algorithms
 * @description: 单指针快速排序，使用栈
 * @author: lld
 * @create: 2021-04-07 17:31
 **/
public class QuickSortByStack {
    public static void quickSort(int[] arr, int startIndex, int endIndex) {
//        使用map存储startIndex和endIndex
        Stack<Map<String, Integer>> stack = new Stack<>();
//        首先存储整体
        Map<String, Integer> map = new HashMap<>();
        map.put("startIndex", startIndex);
        map.put("endIndex", endIndex);
        stack.push(map);

//        当栈不为空
        while (!stack.isEmpty()) {
            Map<String, Integer> params = stack.pop();
            Integer startIndex1 = params.get("startIndex");
            Integer endIndex1 = params.get("endIndex");
            //        获取每次排序的基准值
            int pivot = partition(arr, startIndex1, endIndex1);
//            添加左部分
            if (startIndex1 < pivot - 1) {
                Map<String, Integer> leftPart = new HashMap<>();
                leftPart.put("startIndex", startIndex1);
                leftPart.put("endIndex", pivot - 1);
                stack.push(leftPart);
            }
//            添加右部分
            if (endIndex1 > pivot + 1) {
                Map<String, Integer> rightPart = new HashMap<>();
                rightPart.put("startIndex", pivot + 1);
                rightPart.put("endIndex", endIndex1);
                stack.push(rightPart);
            }
        }

    }

    public static int partition(int[] arr, int startIndex, int endIndex) {
//        基准值选中值
        int pivot = arr[startIndex];
        int mark = startIndex;

        for (int i = startIndex + 1; i <= endIndex; i++) {
            if (arr[i] < pivot) {
                mark++;
                int temp = arr[i];
                arr[i] = arr[mark];
                arr[mark] = temp;
            }
        }
        arr[startIndex] = arr[mark];
        arr[mark] = pivot;
        return mark;
    }

    public static void main(String[] args) {
//        int[] arr = new int[]{4, 7, 6, 5, 3, 2, 8, 1};
//        quickSort(arr, 0, arr.length - 1);
//        System.out.println(Arrays.toString(arr));
        //测试执行效率
        int[] bigArray1 = new int[10000000];
        for (int i = 0; i < bigArray1.length; i++) {
            bigArray1[i] = (int) (Math.random() * 1000000000);
        }
        long start = System.currentTimeMillis();
        quickSort(bigArray1, 0, bigArray1.length - 1);
        long end = System.currentTimeMillis();
        System.out.println("10000000个数据排序时间(毫秒):" + (end - start));//双1500，单1400 栈1700

    }
}
